home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / prlgbnch.lha / qsort.pl < prev    next >
Encoding:
Text File  |  1990-05-26  |  569 b   |  28 lines
  1. % generated: 16 November 1989
  2. % option(s): SOURCE_TRANSFORM_1
  3. %
  4. %   qsort
  5. %
  6. %   David H. D. Warren
  7. %
  8. %   quicksort a list of 50 integers
  9.  
  10. qsort :- qsort([27,74,17,33,94,18,46,83,65, 2,
  11.         32,53,28,85,99,47,28,82, 6,11,
  12.         55,29,39,81,90,37,10, 0,66,51,
  13.          7,21,85,27,31,63,75, 4,95,99,
  14.         11,28,61,74,18,92,40,53,59, 8],_,[]).
  15.  
  16. qsort([X|L],R,R0) :-
  17.     partition(L,X,L1,L2),
  18.     qsort(L2,R1,R0),
  19.     qsort(L1,R,[X|R1]).
  20. qsort([],R,R).
  21.  
  22. partition([X|L],Y,[X|L1],L2) :-
  23.     X =< Y, !,
  24.     partition(L,Y,L1,L2).
  25. partition([X|L],Y,L1,[X|L2]) :-
  26.     partition(L,Y,L1,L2).
  27. partition([],_,[],[]).
  28.